package features.advance.leetcode.array.easy;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author LIN
 * @date 2022-01-17 11:14
 *
 *  219. 存在重复元素 II
 *
 *  难度：简单
 *
 * 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
 * 如果存在，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3,1], k = 3
 * 输出：true
 * 示例 2：
 *
 * 输入：nums = [1,0,1,1], k = 1
 * 输出：true
 * 示例 3：
 *
 * 输入：nums = [1,2,3,1,2,3], k = 2
 * 输出：false
 *
 *
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * 0 <= k <= 105
 *
 *
 */
public class Solution219 {

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        class obj{
            int[] nums;
            int k;
            obj(int[] nums,int k){
                this.nums = nums;
                this.k = k;
            }

            @Override
            public String toString() {
                return "{" +
                        "nums=" + Arrays.toString(nums) +
                        ", k=" + k +
                        '}';
            }
        }

        obj[] test = {
                new obj(new int[]{1,2,3,1},3),
                new obj(new int[]{1,0,1,1},1),
                new obj(new int[]{1,2,3,1,2,3},2)
        };
        for (obj o : test) {
            int[] nums = o.nums;
            int k = o.k;
            boolean containsDuplicate = solution.containsNearbyDuplicate(nums,k);
            System.out.println("Inputs:"+ o +"  Outputs:"+containsDuplicate);
        }


    }

    static class Solution {
        public boolean containsNearbyDuplicate(int[] nums, int k) {
            Map<Integer,Integer> map = new HashMap<>(16);
            for(int i=0;i<nums.length;i++){
                int o = nums[i];
                if(map.containsKey(o)){
                    if(Math.abs(map.get(o)-i) <= k){
                        return true;
                    }
                    map.put(o,i);
                }else{
                    map.put(o,i);
                }
            }
            return false;
        }
    }
}
